home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / MPW_TOOL / TOOLS / TOOLS_WI / ICON_8 / ICONX_FO / FSTRUCT.C < prev    next >
Text File  |  1990-03-02  |  14KB  |  629 lines
  1. /*
  2.  * File: fstruct.c
  3.  *  Contents: delete, get, key, insert, list, member, pop, pull, push, put, set,
  4.  *  table
  5.  */
  6.  
  7. #include "::h:config.h"
  8. #include "::h:rt.h"
  9. #include "rproto.h"
  10.  
  11. #ifdef PreProcess
  12. /* include(../M4/fncs.m4) /* */
  13. /* */
  14. #endif                    /* PreProcess */
  15.  
  16. /*
  17.  * delete(X,x) - delete element x from set or table X if it is there
  18.  *  (always succeeds and returns X).
  19.  */
  20.  
  21. FncDcl(delete,2)
  22.    {
  23.    register union block **pd;
  24.    register uword hn;
  25.    int res;
  26.  
  27.    if (Qual(Arg1))
  28.       RunErr(122, &Arg1);
  29.  
  30.    /*
  31.    * The technique and philosophy here are the same
  32.    *  as used in insert - see comment there.
  33.    */
  34.    switch (Type(Arg1)) {
  35.       case T_Set:
  36.       case T_Table:
  37.          hn = hash(&Arg2);
  38.          pd = memb(BlkLoc(Arg1), &Arg2, hn, &res);
  39.          if (res == 1) {
  40.             /*
  41.             * The element is there so delete it.
  42.             */
  43.             *pd = (*pd)->selem.clink;
  44.             (BlkLoc(Arg1)->set.size)--;
  45.             }
  46.          break;
  47.  
  48.       default:
  49.          RunErr(122, &Arg1);
  50.       }
  51.  
  52.    Arg0 = Arg1;
  53.    Return;
  54.    }
  55.  
  56.  
  57. /*
  58.  * get(x) - get an element from end of list x.
  59.  *  Identical to pop(x).
  60.  */
  61.  
  62. FncDcl(get,1)
  63.    {
  64.    register word i;
  65.    register struct b_list *hp;
  66.    register struct b_lelem *bp;
  67.  
  68.    /*
  69.     * Arg1 must be a list.
  70.     */
  71.    if (Arg1.dword != D_List) 
  72.       RunErr(108, &Arg1);
  73.  
  74.    /*
  75.     * Fail if the list is empty.
  76.     */
  77.    hp = (struct b_list *) BlkLoc(Arg1);
  78.    if (hp->size <= 0)
  79.       Fail;
  80.  
  81.    /*
  82.     * Point bp at the first list block.  If the first block has no
  83.     *  elements in use, point bp at the next list block.
  84.     */
  85.    bp = (struct b_lelem *) hp->listhead;
  86.    if (bp->nused <= 0) {
  87.       bp = (struct b_lelem *) bp->listnext;
  88.       hp->listhead = (union block *) bp;
  89.       bp->listprev = NULL;
  90.       }
  91.    /*
  92.     * Locate first element and assign it to Arg0 for return.
  93.     */
  94.    i = bp->first;
  95.    Arg0 = bp->lslots[i];
  96.    /*
  97.     * Set bp->first to new first element, or 0 if the block is now
  98.     *  empty.  Decrement the usage count for the block and the size
  99.     *  of the list.
  100.     */
  101.    if (++i >= bp->nslots)
  102.       i = 0;
  103.    bp->first = i;
  104.    bp->nused--;
  105.    hp->size--;
  106.    Return;
  107.    }
  108.  
  109. /*
  110.  * key(t) - generate successive keys (entry values) from table t.
  111.  */
  112.  
  113. FncDcl(key,2)
  114.    {
  115.    if (Arg1.dword != D_Table) 
  116.       RunErr(124, &Arg1);
  117.    MakeInt(1, &Arg2);            /* indicate that we want the keys */
  118.    Forward(hgener);            /* go to the hash generator */
  119.    }
  120.  
  121. /*
  122.  * insert(X,x) - insert element x into set or table X if not already there
  123.  *  (always succeeds and returns X).
  124.  */
  125.  
  126. FncDcl(insert,3)
  127.    {
  128.    register union block *bp;
  129.    register union block **pd;
  130.    register struct b_telem *pe;
  131.    register uword hn;
  132.    int res;
  133.  
  134.    if (Qual(Arg1))
  135.       RunErr(122, &Arg1);
  136.  
  137.    switch (Type(Arg1)) {
  138.       case T_Set:
  139.  
  140.          /*
  141.          * We may need at most one new element.
  142.          */
  143.          if (blkreq((word)sizeof(struct b_selem)) == Error) 
  144.             RunErr(0, NULL);
  145.          bp = BlkLoc(Arg1);
  146.          hn = hash(&Arg2);
  147.          /*
  148.           * If Arg2 is a member of set Arg1 then res will have the
  149.           *  value 1 and pd will have a pointer to the pointer
  150.           *  that points to that member.
  151.           *  If Arg2 is not a member of the set then res will have
  152.           *  the value 0 and pd will point to the pointer
  153.           *  which should point to the member - thus we know where
  154.           *  to link in the new element without having to do any
  155.           *  repetitive looking.
  156.           */
  157.          pd = memb(bp, &Arg2, hn, &res);
  158.          if (res == 0) {
  159.             /*
  160.             * The element is not in the set - insert it.
  161.             */
  162.             addmem((struct b_set *)bp, alcselem(&Arg2, hn), pd);
  163.             if (TooCrowded(bp))
  164.                hgrow(&Arg1);
  165.             }
  166.          break;
  167.  
  168.       case T_Table:
  169.          if (blkreq((word)sizeof(struct b_telem)) == Error) 
  170.             RunErr(0, NULL);
  171.          bp = BlkLoc(Arg1);
  172.          hn = hash(&Arg2);
  173.          pd = memb(bp, &Arg2, hn, &res);
  174.          if (res == 0) {
  175.             /*
  176.             * The element is not in the table - insert it.
  177.             */
  178.             bp->table.size++;
  179.             pe = alctelem();
  180.             pe->clink = *pd;
  181.             *pd = (union block *)pe;
  182.             pe->hashnum = hn;
  183.             pe->tref = Arg2;
  184.             pe->tval = Arg3;
  185.             if (TooCrowded(bp))
  186.                hgrow(&Arg1);
  187.             }
  188.          else {
  189.             pe = (struct b_telem *) *pd;
  190.             pe->tval = Arg3;
  191.             }
  192.          break;
  193.  
  194.       default:
  195.          RunErr(122, &Arg1);
  196.       }
  197.  
  198.    Arg0 = Arg1;
  199.    Return;
  200.    }
  201.  
  202. /*
  203.  * list(n,x) - create a list of size n, with initial value x.
  204.  */
  205.  
  206. FncDcl(list,2)
  207.    {
  208.    register word i, size;
  209.    word nslots;
  210.    register struct b_list *hp;
  211.    register struct b_lelem *bp;
  212.  
  213.    if (defshort(&Arg1, 0) == Error) 
  214.       RunErr(0, NULL);
  215.  
  216.    nslots = size = IntVal(Arg1);
  217.  
  218.  
  219.    /*
  220.     * Ensure that the size is positive and that the list-element block 
  221.     *  has MinListSlots slots if its size is zero.
  222.     */
  223.    if (size < 0) 
  224.       RunErr(205, &Arg1);
  225.    if (nslots == 0)
  226.       nslots = MinListSlots;
  227.  
  228.    /*
  229.     * Ensure space for a list-header block, and a list-element block
  230.     * with nslots slots.
  231.     */
  232.    if (blkreq(sizeof(struct b_list) + sizeof(struct b_lelem) +
  233.          (nslots - 1) * sizeof(struct descrip)) == Error) 
  234.       RunErr(0, NULL);
  235.  
  236.    /*
  237.     * Allocate the list-header block and a list-element block.
  238.     *  Note that nslots is the number of slots in the list-element
  239.     *  block while size is the number of elements in the list.
  240.     */
  241.    hp = alclist(size);
  242.    bp = alclstb(nslots, (word)0, size);
  243.    hp->listhead = hp->listtail = (union block *) bp;
  244.  
  245.    /*
  246.     * Initialize each slot.
  247.     */
  248.    for (i = 0; i < size; i++)
  249.       bp->lslots[i] = Arg2;
  250.  
  251.    /*
  252.     * Return the new list.
  253.     */
  254.    Arg0.dword = D_List;
  255.    BlkLoc(Arg0) = (union block *) hp;
  256.    Return;
  257.    }
  258.  
  259. /*
  260.  * member(X,x) - returns x if x is a member of set or table X otherwise fails.
  261.  */
  262.  
  263. FncDcl(member,2)
  264.    {
  265.    int res;
  266.    register uword hn;
  267.  
  268.    if (Qual(Arg1))
  269.       RunErr(122, &Arg1);
  270.  
  271.    switch (Type(Arg1)) {
  272.       case T_Set:
  273.       case T_Table:
  274.          hn = hash(&Arg2);
  275.          memb(BlkLoc(Arg1), &Arg2, hn, &res);
  276.          break;
  277.  
  278.       default:
  279.          RunErr(122, &Arg1);
  280.       }
  281.  
  282.    /* If Arg2 is a member of Arg1 then "res" will have the
  283.     * value 1 otherwise it will have the value 0.
  284.     */
  285.    if (res == 1) {        /* It is a member. */
  286.       Arg0 = Arg2;        /* Return the member if it is in Arg1. */
  287.       Return;
  288.       }
  289.    Fail;
  290.    }
  291.  
  292.  
  293. /*
  294.  * pop(x) - pop an element from beginning of list x.
  295.  */
  296.  
  297. FncDcl(pop,1)
  298.    {
  299.    register word i;
  300.    register struct b_list *hp;
  301.    register struct b_lelem *bp;
  302.  
  303.    /*
  304.     * Arg1 must be a list.
  305.     */
  306.    if (Arg1.dword != D_List) 
  307.       RunErr(108, &Arg1);
  308.  
  309.    /*
  310.     * Fail if the list is empty.
  311.     */
  312.    hp = (struct b_list *) BlkLoc(Arg1);
  313.    if (hp->size <= 0)
  314.       Fail;
  315.  
  316.    /*
  317.     * Point bp to the first list-element block.  If the first block has
  318.     *  no slots in use, point bp at the next list-element block.
  319.     */
  320.    bp = (struct b_lelem *) hp->listhead;
  321.    if (bp->nused <= 0) {
  322.       bp = (struct b_lelem *) bp->listnext;
  323.       hp->listhead = (union block *) bp;
  324.       bp->listprev = NULL;
  325.       }
  326.    /*
  327.     * Locate first element and assign it to Arg0 for return.
  328.     */
  329.    i = bp->first;
  330.    Arg0 = bp->lslots[i];
  331.  
  332.    /*
  333.     * Set bp->first to new first element, or 0 if the block is now
  334.     *  empty.  Decrement the usage count for the block and the size
  335.     *  of the list.
  336.     */
  337.    if (++i >= bp->nslots)
  338.       i = 0;
  339.    bp->first = i;
  340.    bp->nused--;
  341.    hp->size--;
  342.    Return;
  343.    }
  344.  
  345. /*
  346.  * pull(x) - pull an element from end of list x.
  347.  */
  348.  
  349. FncDcl(pull,1)
  350.    {
  351.    register word i;
  352.    register struct b_list *hp;
  353.    register struct b_lelem *bp;
  354.  
  355.    /*
  356.     * Arg1 must be a list.
  357.     */
  358.    if (Arg1.dword != D_List) 
  359.       RunErr(108, &Arg1);
  360.  
  361.    /*
  362.     * Point at list header block and fail if the list is empty.
  363.     */
  364.    hp = (struct b_list *) BlkLoc(Arg1);
  365.    if (hp->size <= 0)
  366.       Fail;
  367.    /*
  368.     * Point bp at the last list element block.  If the last block has no
  369.     *  elements in use, point bp at the previous list element block.
  370.     */
  371.    bp = (struct b_lelem *) hp->listtail;
  372.    if (bp->nused <= 0) {
  373.       bp = (struct b_lelem *) bp->listprev;
  374.       hp->listtail = (union block *) bp;
  375.       bp->listnext = NULL;
  376.       }
  377.    /*
  378.     * Set i to position of last element and assign the element to
  379.     *  Arg0 for return.  Decrement the usage count for the block
  380.     *  and the size of the list.
  381.     */
  382.    i = bp->first + bp->nused - 1;
  383.    if (i >= bp->nslots)
  384.       i -= bp->nslots;
  385.    Arg0 = bp->lslots[i];
  386.    bp->nused--;
  387.    hp->size--;
  388.    Return;
  389.    }
  390.  
  391.  
  392. /*
  393.  * push(x,val) - push val onto beginning of list x.
  394.  */
  395. FncDcl(push,2)
  396.    {
  397.    register word i;
  398.    register struct b_list *hp;
  399.    register struct b_lelem *bp;
  400.    static two = 2;        /* some compilers generat bad code for
  401.                    division by a constant that's a power of 2 */
  402.  
  403.  
  404.    /*
  405.     * Arg1 must be a list.
  406.     */
  407.    if (Arg1.dword != D_List) 
  408.       RunErr(108, &Arg1);
  409.  
  410.    /*
  411.     * Point hp at the list-header block and bp at the first
  412.     *  list-element block.
  413.     */
  414.    hp = (struct b_list *) BlkLoc(Arg1);
  415.    bp = (struct b_lelem *) hp->listhead;
  416.  
  417.    /*
  418.     * If the first list-element block is full, allocate a new
  419.     *  list-element block, make it the first list-element block,
  420.     *  and make it the previous block of the former first list-element
  421.     *  block.
  422.     */
  423.    if (bp->nused >= bp->nslots) {
  424.       /*
  425.        * Set i to the size of block to allocate.
  426.        */
  427.       i = hp->size / two;
  428.       if (i < MinListSlots)
  429.          i = MinListSlots;
  430.  
  431.       /*
  432.        * Ensure space for a new list element block.  If the block can't
  433.        *  be allocated, try smaller blocks.
  434.        */
  435.       while (blkreq((word)sizeof(struct b_lelem) +
  436.             i * sizeof(struct descrip)) == Error) {
  437.         i /= 4;
  438.         if (i < MinListSlots)
  439.            RunErr(0, NULL);
  440.         }
  441.       /*
  442.        * Reset hp in case there was a garbage collection.
  443.        */
  444.       hp = (struct b_list *) BlkLoc(Arg1);
  445.  
  446.       bp = alclstb(i, (word)0, (word)0);
  447.       hp->listhead->lelem.listprev = (union block *) bp;
  448.       bp->listnext = hp->listhead;
  449.       hp->listhead = (union block *) bp;
  450.       }
  451.  
  452.    /*
  453.     * Set i to position of new first element and assign val (Arg2) to
  454.     *  that element.
  455.     */
  456.    i = bp->first - 1;
  457.    if (i < 0)
  458.       i = bp->nslots - 1;
  459.    bp->lslots[i] = Arg2;
  460.    /*
  461.     * Adjust value of location of first element, block usage count,
  462.     *  and current list size.
  463.     */
  464.    bp->first = i;
  465.    bp->nused++;
  466.    hp->size++;
  467.    /*
  468.     * Return the list.
  469.     */
  470.    Arg0 = Arg1;
  471.    Return;
  472.    }
  473.  
  474.  
  475. /*
  476.  * put(x,val) - put val onto end of list x.
  477.  */
  478.  
  479. FncDcl(put,2)
  480.    {
  481.    register word i;
  482.    register struct b_list *hp;
  483.    register struct b_lelem *bp;
  484.    static two = 2;        /* some compilers generate bad code for
  485.                    division by a constant that's a power of 2 */
  486.  
  487.    /*
  488.     * Arg1 must be a list.
  489.     */
  490.    if (Arg1.dword != D_List) 
  491.       RunErr(108, &Arg1);
  492.  
  493.    /*
  494.     * Point hp at the list-header block and bp at the last
  495.     *  list-element block.
  496.     */
  497.    hp = (struct b_list *) BlkLoc(Arg1);
  498.    bp = (struct b_lelem *) hp->listtail;
  499.  
  500.    /*
  501.     * If the last list-element block is full, allocate a new
  502.     *  list-element block, make it the first list-element block,
  503.     *  and make it the next block of the former last list-element
  504.     *  block.
  505.     */
  506.    if (bp->nused >= bp->nslots) {
  507.       /*
  508.        * Set i to the size of block to allocate.
  509.        */
  510.       i = hp->size / two;
  511.       if (i < MinListSlots)
  512.          i = MinListSlots;
  513.  
  514.       /*
  515.        * Ensure space for a new list element block.  If the block can't
  516.        *  be allocated, try smaller blocks.
  517.        */
  518.       while (blkreq((word)sizeof(struct b_lelem) +
  519.             i * sizeof(struct descrip)) == Error) {
  520.         i /= 4;
  521.         if (i < MinListSlots)
  522.            RunErr(0, NULL);
  523.         }
  524.       /*
  525.        * Reset hp in case there was a garbage collection.
  526.        */
  527.       hp = (struct b_list *) BlkLoc(Arg1);
  528.  
  529.       bp = alclstb(i, (word)0, (word)0);
  530.       hp->listtail->lelem.listnext = (union block *) bp;
  531.       bp->listprev = hp->listtail;
  532.       hp->listtail = (union block *) bp;
  533.       }
  534.  
  535.    /*
  536.     * Set i to position of new last element and assign Arg2 to
  537.     *  that element.
  538.     */
  539.    i = bp->first + bp->nused;
  540.    if (i >= bp->nslots)
  541.       i -= bp->nslots;
  542.    bp->lslots[i] = Arg2;
  543.  
  544.    /*
  545.     * Adjust block usage count and current list size.
  546.     */
  547.    bp->nused++;
  548.    hp->size++;
  549.  
  550.    /*
  551.     * Return the list.
  552.     */
  553.    Arg0 = Arg1;
  554.    Return;
  555.    }
  556.  
  557. /*
  558.  * set(list) - create a set with members in list.
  559.  *  The members are linked into hash chains which are
  560.  *  arranged in increasing order by hash number.
  561.  */
  562. FncDcl(set,1)
  563.    {
  564.    register uword hn;
  565.    register dptr pd;
  566.    register union block *ps, *pb;
  567.    struct b_selem *ne;
  568.    union block **pe;
  569.    int res;
  570.    word i, j;
  571.  
  572.    if (ChkNull(Arg1)) {        /* Create empty set */
  573.       ps = hmake(T_Set, (word)0, (word)0);
  574.       if (ps == NULL)
  575.          RunErr(0,NULL);
  576.       Arg0.dword = D_Set;
  577.       BlkLoc(Arg0) = ps;
  578.       Return;
  579.       }
  580.  
  581.    if (Arg1.dword != D_List) 
  582.       RunErr(108, &Arg1);
  583.  
  584.    /*
  585.     * Make a set of the appropriate size.
  586.     */
  587.    ps = hmake(T_Set, (word)0, BlkLoc(Arg1)->list.size);
  588.    if (ps == NULL)
  589.       RunErr(0, NULL);
  590.  
  591.    /*
  592.     * Chain through each list block and for
  593.     *  each element contained in the block
  594.     *  insert the element into the set if not there.
  595.     */
  596.    for (pb = BlkLoc(Arg1)->list.listhead; pb != NULL; pb = pb->lelem.listnext) {
  597.       for (i = 0; i < pb->lelem.nused; i++) {
  598.          j = pb->lelem.first + i;
  599.          if (j >= pb->lelem.nslots)
  600.             j -= pb->lelem.nslots;
  601.          pd = &pb->lelem.lslots[j];
  602.          pe = memb(ps, pd, hn = hash(pd), &res);
  603.          if (res == 0) {
  604.             ne = alcselem(pd,hn);
  605.             addmem((struct b_set *)ps, ne, pe);
  606.             }
  607.          }
  608.       }
  609.    Arg0.dword = D_Set;
  610.    BlkLoc(Arg0) = ps;
  611.    Return;
  612.    }
  613.  
  614. /*
  615.  * table(x) - create a table with default value x.
  616.  */
  617. FncDcl(table,1)
  618.    {
  619.    union block *bp;
  620.  
  621.    bp = hmake(T_Table, (word)0, (word)0);
  622.    if (bp == NULL)
  623.       RunErr(0, NULL);
  624.    bp->table.defvalue = Arg1;
  625.    Arg0.dword = D_Table;
  626.    BlkLoc(Arg0) = bp;
  627.    Return;
  628.    }
  629.